package NO1_Array;

/**
 * 2025-6-23
 * 力扣 - 887.鸡蛋掉落
 * <p>
 * 给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
 * 已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
 * 每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
 * 请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？
 */
public class SuperEggDropMain {
    public static void main(String[] args) {
        int k = 1; // 鸡蛋数
        int n = 2; // 楼层数
        System.out.println(superEggDrop(k, n));
    }

    // 动态规划题目，没看懂
    public static int superEggDrop(int k, int n) {
        // dp[k][m] 表示用 k 枚鸡蛋、最多可以承受 m 次尝试，能确定的最高楼层。
        int m = 0;
        int[] dp = new int[k + 1]; // 当前尝试次数下，各鸡蛋数能覆盖的最大楼层数

        while (dp[k] < n) {
            m++;
            for (int i = k; i > 0; i--) {
                dp[i] = dp[i] + dp[i - 1] + 1;
            }
        }

        return m;
    }
}
